package basic.basic_class01;

import basic.untils.ArrayTestUntil;

public class Code_05_MergeSort {

    // 归并排序
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        mergeSort(arr, 0, arr.length - 1);
    }

    // 分治
    private static void mergeSort(int[] arr, int l, int r) {
        if (l == r) return;
        int mid = l + ((r -l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr,l,mid,r);
    }

    // 归并
    private static void merge(int[] arr, int l, int mid, int r) {
        int[] helper = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while(p1 <= mid && p2 <= r) {
            helper[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid) {
            helper[i++] = arr[p1++];
        }
        while(p2 <= r) {
            helper[i++] = arr[p2++];
        }
        //将辅助的数组拷贝回原数组中
        for (int j = 0; j < helper.length; j++) {
            arr[l + j] = helper[j];
        }
    }

    public static void main(String[] args) {
        int testTime = 500000;  //测试次数
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = ArrayTestUntil.generateRandomArray(maxSize,maxValue);  //生成随机数组
            int[] arr1 = ArrayTestUntil.copyArray(arr);   //复制数组
            mergeSort(arr);
            ArrayTestUntil.comparator(arr1);
            if(!ArrayTestUntil.isEquals(arr,arr1)){
                System.out.println("手撸：" + arr);
                System.out.println("标准：" + arr1);
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking Fucked");
    }
}
